Теорема о СДНФ

Функцию $x \sim y$ иногда удобно записывать как $x^y$ Свойства: $x^1 = x$, $x^0 = \bar{x}$, $1^y = y$, $0^y = \bar{y}$

Любая булева функция, не равная константе $0$, задается некоторой СДНФ.

Пусть $f(x_1, \ldots, x_k)$ отлична от константы $0$. Построим СДНФ $F$ по следующему правилу: для каждого битового вектора $\vec{b} = (b_1, \ldots, b_k)$ такого, что $f(b_1, \ldots, b_k) = 1$, поместим в $F$ элементарную конъюнкцию $C_{\vec{b}} = x_1^{b_1} \land \ldots \land x_k^{b_k}$. Построенная формула — СДНФ по определению. Докажем, что $F$ задает $f$. Функция, заданная ДНФ, равна $1 \iff$ одна из элементарных конъюнкций равна $1$. $$f(b_1, \ldots, b_k) = 1 \iff C_{\vec{b}}(b_1, \ldots, b_k) = 1$$ $\square$

Любую булеву функцию можно привести к ДНФ. $$0 = x\bar{x}$$

ДНФ и СДНФ можно строить преобразованиями, используя законы дистрибутивности, законы де Моргана и пр. $$x \leftrightarrow y = (x \to y)(y \to x) = (\bar{x} \lor y)(\bar{y} \lor x) = \bar{x}\bar{y} \lor 0 \lor 0 \lor xy = \bar{x}\bar{y} \lor xy$$ $$xy = xy(z \lor \bar{z}) = xyz \lor xy\bar{z}$$ В общем случае ДНФ не единственна.